The present invention relates generally to signal processing under Global Positioning System (GPS). In particular, the present invention relates to optimal scheduling for satellite acquisition under GPS, relative to certain search performance criteria.
Location determination using GPS is achieved in a receiver by processing signals received from multiple GPS satellites. The time difference between signal transmission at a GPS satellite and the same signal being received at the receiver provides a range measurement (xe2x80x9cpseudo-rangexe2x80x9d) representative of the distance between the satellite and the receiver. To allow the signal of each GPS satellite to be distinguished from the signals of other GPS satellites, each GPS satellite modulates the carrier signal (1575.42 MHz) with a 1024-chip pseudo-random code (PRN) assigned to that GPS satellite. The PRN has a 1-millisecond period. In theory, the PRNs of the GPS satellites are mutually orthogonal to allow them to be individually recovered at the receiver. Because the position of each satellite at signal transmission time is relatively accurately known, the position of the receiver can be determined in theory using four or more pseudo-ranges from multiple GPS satellites.
The time difference between signal transmission and the signal reaching the receiver is often represented by the quantity xe2x80x9ccode phase,xe2x80x9d which is the time difference modulo the period of the PRN. To obtain a pseudo-range, the receiver processes the signal received, taking into consideration signal and receiver parameters, some of which values are not accurately known a priori. For example, the motion of the satellite relative to the receiver and the imperfection in the receiver clock lead to frequency shifts (xe2x80x9cDoppler effectsxe2x80x9d) in the received signal, known respectively as xe2x80x9csatellite Dopplerxe2x80x9d and xe2x80x9cclock Doppler.xe2x80x9d The receiver""s own motion also contributes a Doppler effect in the received signal. In practice, with a receiver clock accuracy of 1 part per million, the clock Doppler introduces an uncertainty of in the order of 1575 Hz. Because the GPS carrier wavelength is 19 cm., a 1/0.19 Hz uncertainty is introduced per meter per second of receiver velocity; thus a +/xe2x88x92200 Hz uncertainty is introduced for a receiver traveling at a velocity of 85 mph.
To acquire a satellite (i.e., to determine sufficiently accurately the code phase and the Doppler effects as to provide a pseudo-range down to the nano-second range), a receiver may search the code phase and Doppler uncertainty ranges for the code phase and Doppler values that match best with the received signal. In such a search, the present invention provides a search schedule that maximizes certain specified performance criteria (e.g., maximizes the probability for acquiring a satellite within a specified processing time of a digital signal processor).
The present invention provides, in a location determination apparatus, a method for scheduling a search of a parameter space. The method includes (a) dividing the parameter space into search regions, (b) computing a figure of merit associated with each search region, and (c) scheduling a search of the search regions according to optimizing a function of the figure of merit.
In one embodiment of the present invention, a method is provided in a Global Positioning System (GPS) receiver that achieves enhanced performance by scheduling searches in the Doppler search space according to a cost function. In that embodiment, the cost function relates to both the cost of constructing a 3-dimensional correlation grid associated with each GPS satellite, code phase and Doppler range (xe2x80x9cgrid building costxe2x80x9d) and the cost of probing the correlation grid for a maximum correlation value (xe2x80x9csearch costxe2x80x9d). In one implementation, the correlation grid is constructed by creating a table of correlation values for various hypothesized code phase values, integrated over various integration time intervals. The integration can be performed using a fast fourier transform (FFT). Probing this correlation grid is achieved by searching for the integration time, code phase and Doppler values that maximize an xe2x80x9cambiguity functionxe2x80x9d(i.e., the modulus of the complex correlation function resulting from the FFT). (Additional search parameters may include acceleration and the size of coherent blocks in non-coherent combinations). In that implementation, extending integration time intervalsxe2x80x94which enhances the signal-to-noise ration (SNR)xe2x80x94can be achieved by processing incrementally, while changing the range of Doppler values requires recalculating the correlation values.
In addition to a cost function, a method of the present invention includes a reward or value function for each search region. In one instance, the reward function relates to a probability of acquiring a satellite signal in the cells of search region. (A cell is the smallest unit of space within a search region.) By scheduling search of cells having high ratio of reward vis-à-vis cost (i.e., the figure of merit being representative of a constraint maximization), the probability of acquiring satellite is maximized per unit cost. In one instance, the reward function is independent of the Doppler search range and the integration times. In an embodiment described above, the scheduler extends integration time intervals before changing Doppler search ranges, thus optimizes searching of each cell in the grid over various integration times, while rebuilding the grid only when necessary. Cost savings are thus achieved through reduction of grid construction cost.
In one embodiment, after the clock Doppler has been determined upon acquiring one satellite, the Doppler search range associated with a cell in the grid is dominated by the receiver""s own motion. In one embodiment of the present invention, the scheduler schedules searching the Doppler search space using search ranges determined empirically by the expected receiver velocity. In particular, when the receiver experiences a weak signal condition, the scheduling takes advantage of the fact that such a condition also suggests a low receiver velocity. Under such a condition, a tighter Doppler search range is scheduled to decrease search cost, without significantly reducing the probability of signal acquisition.
In one embodiment, an ultra-stacked technique is used.
In one embodiment, the Doppler search expands from a minimum Doppler search range, which is selected for low cost, to a maximum Doppler search range covering substantially all the possible Doppler values. In one implementation, the Doppler search range increases by a factor of 4 to reduce the total cost of rebuilding grid throughout the search. In one implementation, certain search regions having prohibitive costs are not searched.
The present invention is better understood upon consideration of the detailed description below and the accompanying drawings.